What is Computer Science?

• Science of computers (Newell, Perlis, Simon)
• Studies algorithms (Knuth)
• Studies information (Forsythe)
• Natural science of procedures (Shapiro)
• Non-natural science (Simon)
• An engineering field (Brooks)
• Both a science and an engineering field
• New kind of engineering or science (Loui, Hartmanis)
• None of the above
  • Study of complexity
  • Philosophy of procedures
  • Computational thinking
  • Artificial intelligence
  • Magic

Rapaport’s five central questions of CS:

1. a. What can be computed?
   a. How can it be computed?
2. What can be computed efficiently, and how?
3. What can be computed practically, and how?
4. What can be computed physically, and how?
5. What should be computed, and how?

First Steps to Formal Logic

Logic is the business of evaluating arguments; sorting the good from the bad (forallx).

Logic is considered formal when it analyzes and represents argument forms. This is done by symbolizing arguments into a language of logic.

The idea of logical form is central to logic. The logical form of an argument ignores grammatical features irrelevant to logic (such as gender), replacing conjunctions irrelevant to logic (such as ‘but’) with logical ‘and’, regimenting ambiguous logical expressions (such as ‘any’ or ‘every’) with standard logical expressions (such as the universal quantifier $\forall$). Nonlogical content is replaced with schematic letters.

The logical language we’ll first look at, the truth functional logic, is carried over from the boolean algebra, with slight variances. We have the following connectives:

$\neg \land \lor \to \leftrightarrow$, negation, conjunction, disjunction, conditional, and biconditional respectively.

We’ll represent particular atomic sentences with capital A, B, C, ...

We’ll have parentheses for disambiguation ( )

We’ll also use some metalinguistic symbols to help talk about the logic. We’ll use $\mathcal{A}, \mathcal{B}, \mathcal{C}, ...$ as sentence schema (like variables for sentences).

forallx page 44 gives the recursive definition for the truth functional logic. Later on we’ll study a more expressive logic and we’ll add logical vocabulary and grammar to our language.

Arguments

An argument is a set of sentences, one of which is designated the conclusion and the others premises.

We define a valid argument to be an argument where if the premises are true, then the conclusion must also be true.

Consider the following argument:
If every even number greater than 2 has a prime factorization, then every even number greater than 2 is not prime.
Every even number greater than 2 has a prime factorization.
Therefore, every even number greater than 2 is not prime.

We’ll symbolize this argument as follows:
$A \to B$
$A$
$\therefore B$ (the three dots typically represents 'therefore’).

To understand our definition of validity, it’s helpful to look at the truth table for the argument.

$A$	$B$	$A \to B$
T	T	T
T	F	F
F	T	T
F	F	T

The property of being valid for an argument represents a relationship between the possible truth values of the premises and conclusion. In other words, on any row where all of the premises are true, the conclusion is also true. If such conditions do not hold, then the argument is invalid.

In this case, the premises are both true only on the first row. There, the conclusion is also true. There are no other rows where the premises are all true, so the truth value of the conclusion on those rows is of no consequence. So the argument is valid.

Notice that it doesn’t matter what the content of $A$ and $B$ were. Any argument of this form is valid.

Symbolization

Let’s do some more practice.

1. Mark Twain wrote Huckleberry Finn as well as Letters from the Earth.

2. If Sam Clemens called himself “Mark Twain,” he should have put it in quotation marks.

3. Twain wrote Letters from the Earth but he did not write Ecce Homo.

4. Either the author of Joan of Arc and Letters from the Earth wrote Tom Sawyer, or else he wrote A Connecticut Yankee in King Arthur’s Court.

5. In Letters, Satan, Gabriel and Michael all wonder if creating natural law was such a good idea.

6. Satan says something sarcastic and has to leave Heaven for a while; he goes to find Earth.

7. He finds that humans believe that God spends nights sitting up watching over them, but he thinks that either they are just wrong or else they are insane.

8. If they are just wrong, it’s because they don’t think logically.

9. If they are insane, it’s because it’s part of their God-given nature.

10. God says you should forgive, but he forgave neither Adam nor Eve, and he punishes their descendants to this very day.

Other Logical Concepts of Interest

Consistency/Inconsistency
Tautology/Contradiction/Contingency
Logical Equivalence/Inequivalence